import heapq


class Solution(object):
    def kthSmallestPrimeFraction(self, arr, k):
        n = len(arr)
        t = 0
        st = [[arr[0] / arr[n - 1], 0, n - 1]]
        a_set = {(0, n - 1)}
        while True:
            val, i, j = heapq.heappop(st)
            t += 1
            if t == k:
                return [arr[i], arr[j]]
            if j - i > 1:
                if (i, j - 1) not in a_set:
                    heapq.heappush(st, [arr[i] / arr[j - 1], i, j - 1])
                    a_set.add((i, j - 1))
                if (i + 1, j) not in a_set:
                    heapq.heappush(st, [arr[i + 1] / arr[j], i + 1, j])
                    a_set.add((i + 1, j))



data = Solution()
arr = [1, 2, 3, 5, 7]
k = 6
print(data.kthSmallestPrimeFraction(arr, k))
